COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00009 00003	\magnification\magstephalf
C00018 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\parindent 0pt
\parskip 5pt
\line{\sevenrm a12.tex[154,phy] \today\hfill}

\bigskip
\line{CS 154 \hfill SPRING 1984}
\line{Professor Floyd\hfill}
\bigskip
\ctrline{\bf  FINAL EXAMINATION}

\bigskip

{\bf I.}  Closed Book.  Answer T (true) or F (false). (Say true iff always true.)

\smallskip
Let $R$ be a regular set.

    1.  $L$ is regular iff $L∪R$ is regular.

    2.  $L$ is regular iff $L\oplus R$ is regular.  ($\oplus$ is exclusive or, 
also called  symmetric difference.)

    3.  $L$ is regular iff $(L∩R)$ and $(L∪R)$ is regular.

    4.  
    Let $R$ be a finite set.
$L$ is regular iff $L∪R$ is regular.

    5.  If $(L↓1∩L↓2)$ and $(L↓1∪L↓2)$ are both regular then $L↓1$ 
and~$L↓2$ are each regular.

    6.  If $L↓1$  is a DCFL (deterministic context-free language), and $L↓2$ is the  
        image of $L↓1$ under a~DGSM, then $L↓2$ is a~DCFL.

    7.  $\{x\,y\,\hat{x}\}$ is a DCFL ($\hat{x}$ means $x$ in reverse order).

    8.  $\{x\,y\,\hat{x}\hat{y}\}$ is a CFL.

    9.  There is an algorithm which, given an NDPDA, tests whether the 
        language it accepts is empty.

    10. The composition of two PDT's (push-down transducers) is a PDT.

    11. The language $\{a↑ib↑{i+j}c↑j\}$ is a CFL.

    12. CFLs are closed under set difference, $L↓1 -L↓2$.

    13. If $L$ is regular, then $\{x\mid xx\in L\}$ is regular.

    14. If $L$ is regular, then $\{x\mid  x↑{\ast}\subseteq L\}$ is regular.

    15. $\{a↑ib↑jc↑k\mid i≤j≤k\}$ is a CFL.

\vfill\eject

{\bf II.}  Open book.  PROVE EACH ANSWER.

    1.  [5 points.] Are recursively enumerable (RE) sets closed under GSM mappings?

    2.  [5 points.] Are recursive (R) sets closed under GSM mappings?

    3.  [10 points.] Show how to convert a PDA according to Hopcroft \&\ 
Ullman pages 110, 112
        into a flowchart using READ, EOF,  PUSH, POP, START, ACCEPT, 
        REJECT, EMPTY. (Use acceptance by final state.)

    4. [10 points.] Show that (non-deterministic) one-counter machines 
accept all GSM transductions of the one-parenthesis 
         language.


    5. [15 points.] Show that any language accepted by a two-counter machine 
(2CM) is 
        accepted by a composition of two one-counter machines (1CM).  
        Composition of $M↓1$  and~$M↓2$  is defined as for GSMs and PDAs;  output 
        of $M↓1$  is input to~$M↓2$.  Non-determinism is permitted.

    6. [15 points.] A context-free grammar (CFG) may be translated into a set of equations, 
        taking
$$A→BC|DEF|\epsilon$$
        into
$$A=BC+DEF+\{\epsilon\}\,.$$
        Let $L↓A$  be $\{x\mid A\aRa x\}$.  
It was shown in class that the sets $L↓A$, $L↓B$, 
        etc., satisfy the equations.  Some CFGs, however, give rise to
        equations that do not have unique solutions (Example: $S→S|ab$).  
        Give an algorithm to identify CFGs whose equations have unique 
        solutions.
 
7. [10 points.] Is there a context-free grammar for the subset of $(A+B+C+D)↑{\ast}$
in which the number of $A$s equals the numbers of~$B$s, and the number
of $C$s equals the number of~$D$s?

    8. [15 points.] 
Let $L$  be the language of computations of a Turing machine~M.  
Define a computation as a string listing all the states, operations, and
test results through which the machine passes. Assume 1-way or 2-way
infinite tape, as you choose. Show 
        that $\bar{L}$ (the non-computations of M) is accepted by a N1CM (non-
        deterministic 1-counter machine).  [Save this problem for last.  
        Proof is short but proof mechanism is not necessarily obvious.]

\vfill\eject\end
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\parindent 0pt

\line{CS 154 MIDTERM \hfill SPRING 1984}

Results from the course text, handouts or lectures may be used by citation
without proof.  Results from other references may be used without proof only
if accompanied by a copy of the result used.  Prove all answers.

\disleft 20pt:1.:For the following grammar $G$:  
$$\vcenter{\halign{$\rt{#}\;$&$\lft{#}$\cr
S&→aB\mid ba\cr
A&→a\mid aS\mid bAA\cr
B&→b\mid bS\mid aBB\cr}}$$
and the input string $aaabbabbba$, find:

\display 40pt:a.:the leftmost derivation,
\display 40pt:b.:the rightmost derivation,
\display 40pt:c.:the parse tree.

\smallskip
\disleft 20pt:2.:Which of these sets is regular?  Prove your answer.

\display 40pt:a.:The decimal numbers which are multiples of 17.
\display 40pt:b.:The strings of the form
$$x \hbox{ DIVIDES }y$$
where $x$ and $y$ are decimal integers and $x$ does divide $y$ exactly.

\smallskip
\disleft 20pt:3.:The following grammar gives the expressions evaluated 
by a simple pocket calculator that uses Polish postfix notation:
$$E→a\mid b\mid EE+|EE\ast|\,E\sqrt{}\,.$$

\display 40pt:a.:Give the defining descriptions of the prefix equivalence 
classes of this particular language.

\display 40pt:b.:Give the defining descriptions of the infix equivalence 
classes of this particular language.

\disleft 20pt::HINT:  Let the ``weight'' of a string be defined as the number 
of $a$'s and $b$'s, minus the number of $+$'s and 
$\ast$'s.  A string over $=\{a,b,+,\ast,\sqrt{}\}$ belongs
to the language if it has ``weight''~1, and all non-empty prefixes have 
``weight'' $≥1$.  Prove this if you use it.

\smallskip
\disleft 20pt:4.:Construct regular expressions which correspond to the 
following finite automaton transition diagrams:  (text exercises 2.13a and~b).

$$\vcenter{\halign{$\ctr{#}\quad$&$\ctr{#}\quad$&$\ctr{#}\quad$%
&$\ctr{#}\quad$&$\ctr{#}\quad$&$\ctr{#}\qquad\qquad$%
&$\ctr{#}$\xskip&$\ctr{#}$\xskip&$\ctr{#}$\quad%
&$\ctr{#}$\quad&$\ctr{#}$\xskip&$\ctr{#}$\xskip&$\ctr{#}$\cr
&&&0\cr
&\Rightarrow&A&&&&&\Rightarrow&A\cr
\noalign{\medskip}
&0&&1&&&1&&&&0\cr
&&&&&&&1&&0\cr
\noalign{\medskip}
&&1&&&&&&1\cr
C&&&&B&1&C&&&&&B\cr
&&0&&&&&&0\cr}}$$

\medskip
\disleft 20pt:5.:For alphabets $\Sigma$ (``input alphabet'') and
$\Delta$ (``output alphabet''), we
define a set $R$ of formulas (analogous to regular expressions), each of
which designates a relation from $\Sigma↑{\ast}$ to $\Delta↑{\ast}$.

\display 40pt:(1):
$\emptyset$ designates the empty relation.

\display 40pt:(2):
$(x/y)$, where $x\in\Sigma↑{\ast}$, $y\in\Delta↑{\ast}$, 
designates the relation $\{\langle x,y\rangle\}$.

\display 40pt:(3):
If $f↓1$ and $f↓2$ are in $R$, so is $(f↓1f↓2)$, designating the relation
$\{\langle x↓1x↓2,y↓1y↓2\rangle$ for which 
$\langle x↓1,y↓1\rangle\in f↓1$, $\langle x↓2,y↓2\rangle\,f↓2\}$.
So is $(f↓1+f↓2)$, designating the union $f↓1∪f↓2$.

\display 40pt:(4):
If $f\in R$, then $(f↑{\ast})$ designates the relation
$\{\langle x↓1x↓2\ldots x↓n,y↓1y↓2\ldots y↓n\rangle\,,\,n≥0\,,\,
\langle x↓i,y↓i\rangle\in f\}$.

\disleft 20pt::
Show that a relation from $\Sigma↑{\ast}$ to $\Delta↑{\ast}$
is the IO relation of some GSM if and only if some expression 
in~$R$ designates it.

\smallskip
\disleft 20pt:6.:Find a minimum-state finite automaton equivalent to the 
following diagram:  (text exercise 3.25)

$$\vcenter{\halign{$\ctr{#}\quad$&$\ctr{#}\quad$&$\ctr{#}\quad$
&$\ctr{#}\quad$&$\ctr{#}\quad$&$\ctr{#}\quad$&$\ctr{#}\quad$
&$\ctr{#}\quad$&$\ctr{#}\quad$&$\ctr{#}\quad$&$\ctr{#}\quad$
&$\ctr{#}\quad$&$\ctr{#}\quad$&$\ctr{#}\quad$&$\ctr{#}\quad$&$\ctr{#}$\cr
1&&&&&&&0&&&&&&1\cr
&&0&&1&&0&&0&&1&&0&&0\cr
&a&&b&&c&&d&&e&&f&&g&&h\cr
&&0&&1&&&&&&1&&0\cr
\noalign{\smallskip}
&&&1&&&&&&&&1\cr}}$$
				
\smallskip
\disleft 20pt:7.:Given GSM's 
$M↓1$ and $M↓2$, regular sets $R↓1$ and $R↓2$, and the set
$S=\{x\mid \exists y↓1\in R↓1, \exists y↓2\in R↓2,\langle x,y↓1\rangle
\in \hbox{IO}↓{M↓1}, \langle x,y↓2\rangle\in \hbox{IO}↓{M↓2}\}$,
is $S$ regular?  Justify your answer.

\smallskip
\disleft 20pt:8.:If a finite automaton language has $n$ 
prefix-equivalence classes, what
is the largest number of infix-equivalence classes it can have?  Prove your
answer.

\smallskip
\disleft 20pt:9.:Let $S$, $S↓1$, $S↓2$, etc., designate sets, 
and $R$, $R↓1$, $R↓2$, etc., designate relations.

\disleft 20pt::
    Define $R↓1\circ R↓2$ as the composition of the relations (as described in the
handout);
$$\eqalign{S\circ R&=\{y\mid (\exists x\in S) xRy\}\cr
R\circ S&=\{x\mid (\exists y\in S) xRy\}\cr
S↓1\circ S↓2&=\hbox{true if }S↓1∩S↓2≠\emptyset\,.\cr}$$

\disleft 20pt::
Show that the value of $S↓1\circ R↓1\circ R↓2\circ S↓2$ is 
independent of association, for example that:
$$(S↓1\circ R↓1)\circ (R↓2\circ S↓2)=\bigl(S↓1\circ (R↓1\circ R↓2)\bigr)
\circ S↓2\,.$$


Name on paper, legibility and honor code acknowledgement signed.

\vfill\eject\end